// 题目要求：给两个非递减单链表l1, l2，合并为一个非递减的单链表。
// 方法一：迭代求解(不用)
// 技巧：一般创建单链表，都会设一个虚拟头结点，也叫哨兵，因为这样每一个结点都有一个前驱结点。
// 时间复杂度 O(m + n)，空间复杂度 O(1)

// 方法二：递归求解
// 核心思路: 1.递归出口：链表头指针为空时，返回什么？(链表1为空，返回2头指针，反之返回1头指针)
// 2.递归必须缩小区间，如何缩小区间？(跟迭代方法中的一样，如果PHead1的所指节点值小于等于pHead2所指的结点值，那么 pHead1 后续节点和 pHead2 节点继续递归，否则pHead2 后续节点和 pHead1 节点继续递归)
// 时间复杂度：O(m+n)，空间复杂度：O(m+n),每一次递归，递归栈都会保存一个变量，最差情况会保存(m+n)个变量

function ListNode(x) {
  this.val = x;
  this.next = null;
}
function Merge(pHead1, pHead2) {
  if (!pHead1) return pHead2
  if (!pHead2) return pHead1
  if (pHead1.val <= pHead2.val) {
    pHead1.next = Merge(pHead1.next, pHead2)
    return pHead1
  } else {
    pHead2.next = Merge(pHead2.next, pHead1)
    return pHead2
  }
}
module.exports = {
  Merge: Merge
};